package tree.leetcode_572;

public class IsSubTree {
    public boolean isSubTree(TreeNode s, TreeNode t){
        //s 为 null ，匹配失败,返回false;
        if(s == null) return false;
        //t 为 null ，匹配成功
        if(t == null) return true;

        //两树不相同时，执行isSubTree()
        //isSubTree()函数相当于是一个搜索过程，寻找s树中和t值相同的节点。
        return isSameTree(s,t) || isSubTree(s.left,t) || isSubTree(s.right,t);
    }
    public boolean isSameTree(TreeNode p,TreeNode q){
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}
